import java.util.ArrayList;
import java.util.Random;

/**
 *  This class provides all the genetic operators for building the network
 * population
 *
 */
public class PopulationBuilder {

	Random rand = new Random();
	
	/**
	 this method builds a new sorting network population
	 *
	 * @param population
	 * @param newPopulation
	 * @param fitness
	 */
	public void buildNewPopulation(SortingNetwork[] population,
			SortingNetwork[] newPopulation, int[] fitness) {
		selectElitism(population, newPopulation, fitness, Constants.ELITISM_COUNT);
		preformCrossovers(population, newPopulation, fitness, Constants.POPULATION_SIZE-Constants.ELITISM_COUNT);
		
	}
	
	/**
	 *This method performs crossovers on the population
	 * it creates two children in each iteration: 
	 * it takes two parents and choose position on each of them
	 * then, joining the start of the parent to the end of the other parent
	 * 
	 * 
	 * @param population - the old population
	 * @param newPopulation - the new population
	 * @param fitness - array of fitness of the population networks
	 * 
	 */
	public void preformCrossovers(SortingNetwork[] population,SortingNetwork[] newPopulation,
			int[] fitness, int fillSize) {
		
		int fromPosition = Constants.POPULATION_SIZE-fillSize;
		for (int i = fromPosition; i < Constants.POPULATION_SIZE; i+=2) {
			SortingNetwork p1= getParent(population,fitness);
			SortingNetwork p2= getParent(population,fitness);
			
			int position1= rand.nextInt(p1.getNetwork().size());
			int position2= rand.nextInt(p2.getNetwork().size());
			
			ArrayList<Integer> child1=new ArrayList<Integer>();
			ArrayList<Integer> child2=new ArrayList<Integer>();
			
			
			for (int j=0; j < position1; j++) {
				child1.add(p1.getNetwork().get(j));
			}
			for (int j=position2; j < p2.getNetwork().size(); j++) {
				child1.add(p2.getNetwork().get(j));
			}
			for (int j=0; j < position2; j++) {
				child2.add(p2.getNetwork().get(j));
			}
			for (int j=position1; j < p1.getNetwork().size(); j++) {
				child2.add(p1.getNetwork().get(j));
			}
			
			SortingNetwork s1=new SortingNetwork(child1) ;
			SortingNetwork s2=new SortingNetwork(child2);
			mutateNetwork(s1);
			mutateNetwork(s2);
			newPopulation[i]= s1;
			newPopulation[i+1]= s2;
		}
		
		
	}
	/**
	 * this method performs mutation on a sorting network
	 * if flips one of the edges to a different number
	 * 
	 * @param s1
	 */
	private void mutateNetwork(SortingNetwork s1) {
		for (int i = 0; i < s1.getNetwork().size(); i++) {
			double p = rand.nextDouble();
			if (p<Constants.MUTATION_PROBABILITY){
				s1.getNetwork().remove(i);
				s1.getNetwork().add(i,rand.nextInt(SortingNetwork.edgesCode.length));
			}
		}
		
	}
	/**
	 * This method creates elitisim meaning few best sorting networks moves as they are to the new population 
	 * without any mutation
	 * 
	 * @param population
	 * @param newPopulation
	 * @param fitness
	 * @param elitismCount - the number of best sorting networks 
	 */

	public void selectElitism(SortingNetwork[] population,SortingNetwork[] newPopulation,int[] fitness, int elitismCount) {
		boolean[] indexes=new boolean[population.length];
		for(int i=0; i<elitismCount; i++)
		{
			int max=-1;
			int index=-1;
			for(int j=0 ;j<fitness.length; j++)
			{
				if(fitness[j]>max && !indexes[j])
				{
					max=fitness[j];
					index=j;
				}
			}
			indexes[index]=true;
			newPopulation[i]=population[index];
		}
		
		
	}
	/**
	 * This method returns a random parent according to the fitness.
	 * the higher fitness the higher probability
	 * 
	 * @param population
	 * @param fitness
	 * @return
	 */
	private SortingNetwork getParent(SortingNetwork[] population,int[] fitness) {
		int  sum =0;
		for (int i : fitness) {
			sum+=i;
		}
		
		
		int p = rand.nextInt(sum);
		sum=0;
		for (int i = 0; i < fitness.length; i++) {
			sum+=fitness[i];
			if (p<sum)
				return population[i];
		}
		
		return population[population.length];
	}
	


}
